#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int KeyType;
typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BiTree;

//因为存在随机数的问题，所以难免会有数值相等的情况，敬请理解！
//正常写建议写死
//非递归创建二叉查找树
int BST_Insert(BiTree &T, KeyType k) {
    BiTree tree_new = (BiTree) calloc(1, sizeof(BSTNode));
    //将传入的值放入申请的结点中
    tree_new->key = k;
    //分两种情况：树为空的情况和树不为空的情况
    if (T == NULL) {
        //如果树为空，将传入新结点作为树的根节点
        T = tree_new;
        return 0;
    }
    BiTree p = T, parent;//用来遍历
    //本质上来说是将根节点不断重新赋值进行下移比较
    //知道找到要插入结点的父亲节点
    while (p) {
        parent = p;//用来存取p的父亲
        if (k > p->key) {
            p = p->rchild;//去跟p的右边找（将p的右结点赋给p）相当于下一次遍历和p的右结点进行比较
        } else if (k < p->key) {
            p = p->lchild;
        } else {
            return 0;//相等的元素不可以放入查找树，考研不会考相等元素放入问题
        }
    }
    //接下来要判断放到父亲的左边还是右边
    if (k > parent->key) {
        //大于放到父亲右边
        parent->rchild = tree_new;
    } else {
        //小于放到父亲左边
        parent->lchild = tree_new;
    }
    return 1;
}

//递归写法，很是巧妙，妙哉，建议细品
int BST_Insert_Recursion(BiTree &tree, KeyType k) {
    if (tree == NULL) {
        tree = (BiTree) calloc(1, sizeof(BSTNode));
        tree->key = k;
        return 1;
    } else if (tree->key == k) {
        return 0;
        //k小于当前根节点结点值的情况
    } else if (k < tree->key) {
        return BST_Insert_Recursion(tree->lchild, k);
    } else {
        //k大于当前根结点值的情况
        return BST_Insert_Recursion(tree->rchild, k);
    }
}

//创建二叉排序树
void Create_BST(BiTree &T, KeyType *str, int len) {
    int i = 0;
    for (i = 0; i < len; i++) {
        //以下方法二者选其一即可
//        BST_Insert(T, str[i]);
        BST_Insert_Recursion(T, str[i]);
    }
}

//中序遍历
void InOrder(BiTree tree) {
    if (tree != NULL) {
        InOrder(tree->lchild);
        printf("%2d ", tree->key);
        InOrder(tree->rchild);
    }
}

BiTree BST_Search(BiTree tree, KeyType num, BiTree &parent) {
    parent = NULL;
    //如果num==tree->key就直接结束循环返回该结点地址
    while (tree != NULL && num != tree->key) {
        parent = tree;
        //如果当前要查找的值大于根节点的值
        if (num > tree->key) {
            tree = tree->rchild;
        } else {
            tree = tree->lchild;
        }
    }
    return tree;
}

//二叉排序树(又叫二叉查找树) 新建、中序遍历、查找
int main() {
    BiTree tree = NULL;//树根
    BiTree parent;//存储父亲结点的地址值
    BiTree search;
    KeyType num;
    KeyType str[7];
    srand(time(NULL));
    //随机生成7个元素进入到二叉排序树中
    //不建议使用随机数放入二叉排序树，因为会出现数组中两个值相同的情况
    for (int &i : str) {
        i = rand() % 100;
    }
    for (int i:str) {
        printf("%2d ", i);
    }
    //创建二叉查找树
    //create Binary Search Tree
    Create_BST(tree, str, 7);
    printf("\n");
    //中序遍历是按从小到大的顺序
    InOrder(tree);
    printf("\n");
    printf("Please enter the value you want to search:\n");
    scanf("%d", &num);
    search = BST_Search(tree, num, parent);
    if (search) {
        printf("Search successfully,and the value is %d\n", search->key);
    } else {
        printf("Search failed\n");//没有找到该结点返回的是NULL
    }
    return 0;
}
